package datastructure.book.tujiesuanfa.queueastack.solution._2_more;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;

/**
 *  最小栈 提供 push ，pop ，top 操作，
 *  并能在常数时间内检索到最小元素的栈
 *  每个函数O(1)时间复杂度
 */
public class MinStack {

    private final Deque<Integer> stack = new LinkedList<>();
    private final Deque<Integer> minList = new LinkedList<>();

    public MinStack() {

    }

    public void push(int x) {
        stack.add(x);
        Integer i = minList.peekLast();
        if (i == null || i >= x) {
            minList.add(x);
        }
    }

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        Integer pop = stack.removeLast();
        Integer i = minList.peekLast();
        if (Objects.equals(pop, i)) {
            minList.removeLast();
        }
    }

    public int top() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.peekLast();
    }

    public int getMin() {
        if (minList.isEmpty()) {
            return -1;
        }
        return minList.peekLast();
    }
}
